#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define inf 0x3f3f3f3f
#define maxn 80005
struct node{ int v,rnd,sz,w,l,r; }tr[maxn*17];
int cnt,v[maxn<<1],next[maxn<<1],first[maxn];
int dfn,fa[maxn],dep[maxn],top[maxn],ma[maxn],rma[maxn],son[maxn],size[maxn];
int nd,root[maxn<<2],n,haha[maxn];
void add(int st,int end){
	v[++cnt]=end;
	next[cnt]=first[st];
	first[st]=cnt;
}
void dfs(int x){
	son[x]=0,size[x]=1;
	for(int e=first[x];e;e=next[e]){
		if(v[e]!=fa[x]){
			fa[v[e]]=x,dep[v[e]]=dep[x]+1;
			dfs(v[e]);
			if(size[v[e]]>size[son[x]])son[x]=v[e];
			size[x]+=size[v[e]];
		}
	}
}
void mama(int x,int anc){
	ma[x]=++dfn,rma[dfn]=x;
	top[x]=anc;
	if(son[x])mama(son[x],anc);
	for(int e=first[x];e;e=next[e])
		if(v[e]!=fa[x]&&v[e]!=son[x])mama(v[e],v[e]);
}
int newnode(int x){
	int k=++nd;
	tr[k].v=x,tr[k].rnd=rand();
	tr[k].w=tr[k].sz=1;
	return k;
}
void push_up(int k){
	tr[k].sz=tr[tr[k].l].sz+tr[k].w+tr[tr[k].r].sz;
}
void lturn(int &k){
	int t=tr[k].r;
	tr[k].r=tr[t].l,tr[t].l=k;
	tr[t].sz=tr[k].sz,push_up(k),k=t;
}
void rturn(int &k){
	int t=tr[k].l;
	tr[k].l=tr[t].r,tr[t].r=k;
	tr[t].sz=tr[k].sz,push_up(k),k=t;
}
void insert_y(int &k,int x){
	if(!k){
		k=newnode(x);
		return;
	}
	if(x==tr[k].v)tr[k].w++;
	else if(x>tr[k].v){
		insert_y(tr[k].l,x);
		if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
	}
	else{
		insert_y(tr[k].r,x);
		if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
	}
	push_up(k);
}
void update_x(int rt,int l,int r,int pos,int x){
	insert_y(root[rt],x);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(pos<=mid)update_x(lson,pos,x);
	else update_x(rson,pos,x);
}
void del_y(int &k,int x){
	if(x==tr[k].v){
		if(tr[k].w>1)tr[k].w--;
		else if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
		else{
			if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
				rturn(k),del_y(k,x);
			else lturn(k),del_y(k,x);
		}
	}
	else if(x>tr[k].v)del_y(tr[k].l,x);
	else del_y(tr[k].r,x);
	push_up(k);
}
void del_x(int rt,int l,int r,int pos,int x){
	del_y(root[rt],x);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(pos<=mid)del_x(lson,pos,x);
	else del_x(rson,pos,x);
}
int query_y(int k,int x){
	if(!k)return 0;
	if(x==tr[k].v)return tr[tr[k].l].sz+tr[k].w;
	else if(x>tr[k].v)return query_y(tr[k].l,x);
	else return tr[tr[k].l].sz+tr[k].w+query_y(tr[k].r,x);
}
int query_x(int rt,int l,int r,int ql,int qr,int x){
	if(ql<=l&&qr>=r)return query_y(root[rt],x);
	int mid=(l+r)>>1,ans=0;
	if(ql<=mid)ans+=query_x(lson,ql,qr,x);
	if(qr>mid)ans+=query_x(rson,ql,qr,x);
	return ans;
}
int query_op(int a,int b,int x){
	int ans=0;
	while(top[a]!=top[b]){
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		ans+=query_x(1,1,n,ma[top[a]],ma[a],x);
		a=fa[top[a]];
	}
	if(dep[a]<dep[b])swap(a,b);
	ans+=query_x(1,1,n,ma[b],ma[a],x);
	return ans;
}
int solve(int a,int b,int k){
	int l=-1,r=inf;
	while(l<r-1){
		int mid=(l+r)>>1;
		if(query_op(a,b,mid)>=k)l=mid;
		else r=mid;
	}
	return l;
}
int main(){
	int m,a,b,k;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&haha[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	dfs(1),mama(1,1);
	for(int i=1;i<=n;i++)
		update_x(1,1,n,ma[i],haha[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&k,&a,&b);
		if(k==0){
			del_x(1,1,n,ma[a],haha[a]);
			haha[a]=b;
			update_x(1,1,n,ma[a],haha[a]);
		}
		else{
			int x=solve(a,b,k);
			if(x!=-1)printf("%d\n",x);
			else puts("invalid request!");
		}
	}
	return 0;
}

